/**
 * 解题思路：
 * 1、状态
 * f[i][j] 表示 s 的第 i 个字符到第 j 个字符组成的子串中，最长的回文序列长度是多少。
 * 2、转移方程
 * 如果 s 的第 i 个字符和第 j 个字符相同的话
 * f[i][j] = f[i + 1][j - 1] + 2
 * 如果 s 的第 i 个字符和第 j 个字符不同的话
 * f[i][j] = max(f[i + 1][j], f[i][j - 1])
 * 然后注意遍历顺序，i 从最后一个字符开始往前遍历，j 从 i + 1 开始往后遍历，这样可以保证每个子问题都已经算好了。
 * 初始化
 * 由于任何长度为 11 的子序列都是回文子序列
 * f[i][i] = 1 单个字符的最长回文序列是 1
 * 结果
 * f[0][n - 1]
 *
 */
public class LongestPalindromicSubsequence2 {
    public static void main(String[] args) {
        System.out.println(longestPalindromeSubseq("abbbb"));
    }
    public static int longestPalindromeSubseq(String s) {
        int n=s.length();
        int[][] dp=new int[n][n];
        /**
         * 状态转移方程：dp[i][j]= dp[i+1][j-1]+2   if(s[i]==s[j])
         *                        max(dp[i][j-1],dp[i+1][j])  否则
         * */
        for (int i = n-1; i >=0; i--) {// i=n-1为什么不是i=0，因为dp[0][j]=dp[1][j-1]这个数还没赋值
            char c=s.charAt(i);
            dp[i][i]=1;
            for (int j = i+1; j < n; j++) {
                if(c==s.charAt(j)){
                    dp[i][j]=dp[i+1][j-1]+2;
                }else{
                    dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return dp[0][n-1];
    }
}
